home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / LIB_INFO.ZIP / LIBDICT.TXT < prev    next >
Text File  |  1993-11-15  |  4KB  |  130 lines
  1.  
  2. Document ID: Q71891
  3.  
  4. Product: Microsoft EXEMOD, EXEPACK, or LIB Utility
  5. Title: Dictionary Hashing Algorithm Used by the LIB Utility
  6.  
  7. Updated: 16-MAY-1991
  8. Operating System Versions: 3.0X 3.10 3.11 3.14 3.15 3.17 3.18 | 3.1
  9. Operating Systems: MS-DOS                             | OS/2
  10.  
  11. Summary:
  12.  
  13. The last part of each library produced by the Microsoft Library
  14. Manager (LIB) contains a dictionary that holds all the public symbols
  15. in the library. The hashing algorithm mentioned on page 63 of the
  16. "Microsoft C Developer's Toolkit Reference" is used to place data in
  17. the dictionary. The code required to implement the hashing algorithm
  18. is shown at the end of this article.
  19.  
  20. More Information:
  21.  
  22. The library dictionary is divided into pages that are 512 bytes long.
  23. Each page starts with a 37-byte bucket table, which contains 37
  24. separate offsets to the symbols in the rest of the page. The values in
  25. the buckets are multiplied by 2 to get the actual offset (since 1 byte
  26. can contain only 256 different values).
  27.  
  28. The hashing algorithm analyzes a symbol's name and produces two
  29. indexes (page index and bucket index) and two deltas (page index delta
  30. and bucket index delta). Using the offset contained in the bucket at
  31. bucket index in the page at page index, you must compare the symbol at
  32. that location with the one you are looking for.
  33.  
  34. If (due to symbol collision) you have not found the correct symbol,
  35. add the bucket index delta to the current bucket index, modulo 37, and
  36. try again. Continue until all the buckets in the current page are
  37. tried. Then, add the page index delta to the current page, modulo by
  38. the page count, and try all the buckets in that page starting at
  39. bucket index. Continue this process until all of the possible page and
  40. offset combinations have been tried.
  41.  
  42. For more information on the actual format of the symbols in the
  43. dictionary, and information on the format for the rest of the library,
  44. see the "Microsoft C Developer's Toolkit Reference."
  45.  
  46. Sample Code
  47. -----------
  48.  
  49. /* This code illustrates the hashing algorithm used by LIB */
  50.  
  51. /* Compile options needed: none
  52. */
  53.  
  54. #include <stdio.h>
  55. #include <string.h>
  56. #include <malloc.h>
  57. #include <stdlib.h>
  58.  
  59. #define XOR ^
  60. #define MODULO %
  61.  
  62. char *symbol;        /* Symbol to find (or to place) */
  63. int dictlength;      /* Dictionary length in pages   */
  64. int buckets;         /* Number of buckets on one page */
  65.  
  66. char *pb;            /* A pointer to the beginning of the symbol */
  67. char *pe;            /* A pointer to the end of the symbol */
  68. int slength;         /* Length of the symbol's name */
  69.  
  70. int page_index;         /* Page Index */
  71. int page_index_delta;   /* Page Index Delta */
  72. int bucket_index;       /* Bucket Index */
  73. int bucket_index_delta; /* Bucket Index Delta */
  74.  
  75. unsigned c;
  76.  
  77. void hash(void)
  78. {
  79.    page_index = 0;
  80.    page_index_delta = 0;
  81.    bucket_index = 0;
  82.    bucket_index_delta = 0;
  83.  
  84.    while( slength--)
  85.    {
  86.       c = *(pb++) | 32;        /* Convert character to lower case */
  87.       page_index = (page_index<<2) XOR c;                 /* Hash */
  88.       bucket_index_delta = (bucket_index_delta>>2) XOR c; /* Hash */
  89.       c = *(pe--) | 32;
  90.       bucket_index = (bucket_index>>2) XOR c;             /* Hash */
  91.       page_index_delta = (page_index_delta<<2) XOR c;     /* Hash */
  92.    }
  93.    /* Calculate page index  */
  94.    page_index = page_index MODULO dictlength;
  95.  
  96.    /* Calculate page index delta */
  97.    if( (page_index_delta = page_index_delta MODULO dictlength) == 0)
  98.       page_index_delta = 1;
  99.  
  100.    /* Calculate bucket offset */
  101.       bucket_index = bucket_index MODULO buckets;
  102.  
  103.    /* Calculate bucket offset delta */
  104.    if( (bucket_index_delta = bucket_index_delta MODULO buckets) == 0)
  105.       bucket_index_delta = 1;
  106. }
  107.  
  108. void main(void)
  109. {
  110.    int i;
  111.    dictlength = 3;
  112.    buckets = 37;
  113.  
  114.    if ( (symbol = (char *) malloc( sizeof(char) * 4 )) == NULL )
  115.       exit(1);
  116.  
  117.    strcpy( symbol, "one");
  118.  
  119.    for( i = 0; i < 2; i++ )   {
  120.       slength = strlen(symbol);
  121.       pb = symbol;
  122.       pe = symbol + slength ;
  123.       hash();
  124.       printf("\npage_index:  %2d   page_index_delta:  %d",
  125.       page_index, page_index_delta);
  126.       printf("\nbucket_index: %2d   bucket_index_delta: %d",
  127.       bucket_index, bucket_index_delta);
  128.       strcpy( symbol, "two");
  129.    }
  130.